package com.example.demo.leetcode.classics150;

import java.util.LinkedList;
import java.util.Queue;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _95蛇梯棋
 * @description
 * @date 2023/08/08 16:46
 * <p>
 * ******************************************************
 */
public class _95蛇梯棋 {


    /**
     * 给你一个大小为 n x n 的整数矩阵 board ，方格按从 1 到 n2 编号，编号遵循 转行交替方式 ，
     * 从左下角开始 （即，从 board[n - 1][0] 开始）每一行交替方向。
     * <p>
     * 玩家从棋盘上的方格 1 （总是在最后一行、第一列）开始出发。
     * <p>
     * 每一回合，玩家需要从当前方格 curr 开始出发，按下述要求前进：
     * <p>
     * 选定目标方格 next ，目标方格的编号符合范围 [curr + 1, min(curr + 6, n2)] 。
     * 该选择模拟了掷 六面体骰子 的情景，无论棋盘大小如何，玩家最多只能有 6 个目的地。
     * 传送玩家：如果目标方格 next 处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格 next 。
     * 当玩家到达编号 n2 的方格时，游戏结束。
     * r 行 c 列的棋盘，按前述方法编号，棋盘格中可能存在 “蛇” 或 “梯子”；如果 board[r][c] != -1，
     * 那个蛇或梯子的目的地将会是 board[r][c]。编号为 1 和 n2 的方格上没有蛇或梯子。
     * <p>
     * 注意，玩家在每回合的前进过程中最多只能爬过蛇或梯子一次：就算目的地是另一条蛇或梯子的起点，玩家也 不能 继续移动。
     * <p>
     * 举个例子，假设棋盘是 [[-1,4],[-1,3]] ，第一次移动，玩家的目标方格是 2 。
     * 那么这个玩家将会顺着梯子到达方格 3 ，但 不能 顺着方格 3 上的梯子前往方格 4 。
     * 返回达到编号为 n2 的方格所需的最少移动次数，如果不可能，则返回 -1。
     *
     * @param board
     * @return
     */
//    public int snakesAndLadders0(int[][] board) {
//        onPath = new boolean[board.length * board.length + 1];
//        bfs(board, 1, false, 0);
//        return res == Integer.MAX_VALUE ? -1 : res;
//    }
//
//    int res = Integer.MAX_VALUE;
//    boolean[] onPath;
//
//    private void bfs(int[][] board, int curr, boolean isSnake, int count) {
//        if (onPath[curr]) {
//            return;
//        }
//        int n = board.length;
//        if (curr >= (n * n)) {
//            res = Math.min(res, count);
//            return;
//        }
//        if (count >= res) {
//            return;
//        }
//        onPath[curr] =true;
//        int currValue = getCurrValue(board, n, curr);
//        if (!isSnake && currValue > 0 && currValue > curr) {
//            bfs(board, currValue, true, count);
//            return;
//        }
//
//        int nextMax = Math.min((n * n), curr + 6);
//        for (int i = curr + 1; i <= nextMax; i++) {
//            int item = getCurrValue(board, n, i);
//            if (item == -1 || item > curr) {
//                bfs(board, i, false, count + 1);
//            }
//        }
//        onPath[curr] =false;
//    }
//
//    private int getCurrValue(int[][] board, int n, int curr) {
//        int i = (curr - 1) / n;
//        // 等于0代表从左向右，等于1代表从右向左
//        int left = i % 2;
//        int j = curr % n;
//        if (left == 0) {
//            j = (j - 1 + n) % n;
//        } else {
//            j = (n - j) % n;
//        }
//        i = (n - i - 1) % n;
//        return board[i][j];
//    }


    public int snakesAndLadders(int[][] board) {
        int n = board.length, k = 1;
        int[] nums = new int[n * n + 1];
        boolean[] visit = new boolean[n * n + 1];
        while (k <= n * n) {  // 用一维数组记录每个方格对应的值，也可以用map记录，但数组效率更高
            int row = n - 1 - (k - 1) / n;
            int col = ((k - 1) / n % 2 == 0) ? (k - 1) % n : (n - 1) - (k - 1) % n;
            nums[k++] = board[row][col];
        }
        Queue<Integer> pq = new LinkedList<>();
        int start = 1, step = 0;
        pq.add(1);
        while (!pq.isEmpty()) {  //bfs广度遍历图，找到最短路径
            int num = pq.size();
            // 类似层次遍历
            for (int i = 0; i < num; i++) {
                start = pq.poll();
                if (start == n * n) return step;
                for (int j = 1; j < 7 && start + j <= n * n; j++) {
                    int num1 = nums[start + j];
                    int loca = (num1 == -1) ? start + j : num1;
                    if (!visit[loca]) {
                        pq.add(loca);
                        visit[loca] = true;
                    }
                }
            }
            step++;
        }
        return -1;
    }


    public static void main(String[] args) {
        _95蛇梯棋 s = new _95蛇梯棋();
        for (int i = 1; i <= 36; i++) {
            System.out.println(s.snakesAndLadders(new int[][]{{-1, -1, -1, -1, -1, -1}
                    , {-1, -1, -1, -1, -1, -1}
                    , {-1, -1, -1, -1, -1, -1}
                    , {-1, 35, -1, -1, 13, -1}
                    , {-1, -1, -1, -1, -1, -1}
                    , {-1, 15, -1, -1, -1, -1}}));
        }
    }
}
